/*************************************************************************
	> File Name: 003.HZOJ333.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  2/22 22:34:01 2021
 ************************************************************************/

/**
 *
 *
 * 题目描述
给定长度为𝑁的数列𝐴，以及𝑀条指令 (N≤500000, M≤100000)，每条指令可能是以下两种之一：

“2 x y”，把 A[x] 改成 y。

“1 x y”，查询区间 [x,y] 中的最大连续子段和，即𝑚𝑎𝑥(𝑥≤𝑙≤𝑟≤𝑦)∑𝑟𝑖=𝑙𝐴[𝑖]。

对于每个询问，输出一个整数表示答案。

输入
第一行两个整数𝑁(1≤𝑁≤500000),𝑀(1≤𝑀≤100000)
第二行𝑁个整数𝐴𝑖(1≤|𝐴𝑖|≤1000)
接下来𝑀行每行3个整数𝑘,𝑥,𝑦，𝑘=1表示查询（此时如果x>y，请交换x,y），𝑘=2表示修改

输出
对于每个询问输出一个整数表示答案。
*/


#include <iostream>
#include <cstdio>
using namespace std;

#define MAX_N 500000

struct Data{
    int sum;
    int lmax;
    int inmax;
    int rmax;
} _tree[MAX_N << 2];
Data *tree = _tree + 1;

int arr[MAX_N + 5];
int n, m, flag;

void UP(int ind, int lind, int rind) {
    tree[ind].sum = tree[lind].sum + tree[rind].sum;
    tree[ind].lmax = max(tree[lind].lmax, tree[lind].sum + tree[rind].lmax);
    tree[ind].rmax = max(tree[rind].rmax, tree[rind].sum + tree[lind].rmax);
    tree[ind].inmax = max(max(tree[lind].inmax, tree[rind].inmax), tree[lind].rmax + tree[rind].lmax);
    return ;
}

void build(int ind, int l, int r) {
    if (l == r) {
        tree[ind].sum = tree[ind].lmax = tree[ind].inmax = tree[ind].rmax = arr[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ind << 1, l, mid);
    build(ind << 1 | 1, mid + 1, r);
    UP(ind, ind << 1, ind << 1 | 1);
    return ;
}

void modify(int ind, int l, int r, int i, int val) {
    if (l == r) {
        tree[ind].sum = tree[ind].lmax = tree[ind].inmax = tree[ind].rmax = val;
        return ;
    }
    int mid = (l + r) >> 1;
    if (i <= mid) {
        modify(ind << 1, l, mid, i, val);
    } else {
        modify(ind << 1 | 1, mid + 1, r, i, val);
    }
    UP(ind, ind << 1, ind << 1 | 1);
    return ;
}

void query(int ind, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        if (flag) {
            tree[0] = tree[ind];
            flag = 0;
        } else {
            UP(-1, 0, ind);
            tree[0] = tree[-1];
        }
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        query(ind << 1, l, mid, x, y);
    }
    if (mid < y) {
        query(ind << 1 | 1, mid + 1, r, x, y);
    }
    return ;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", arr + i);
    build(1, 1, n);

    for (int i = 0; i < m; i++) {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        switch (k) {
            case 1: {
                if (x > y) swap(x, y);
                flag = 1;
                query(1, 1, n, x, y);
                printf("%d\n", tree[0].inmax);
            } break;
            case 2: {
                modify(1, 1, n, x, y);
            } break;
        }
    }
    return 0;
}
